package org.labuladong.经典贪心算法;

import com.sun.org.apache.bcel.internal.generic.RETURN;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-22:49
 * @Description:
 *
 * 标签：动态规划，贪⼼算法，⼀维动态规划
 * 给你⼀个⾮负整数数组 nums，你最初位于数组的第⼀个位置，数组中的每个元素代表你在该位置可以跳跃的最⼤⻓度，请你使⽤最少的跳跃次数到达数组的最后⼀个位置（假设你总是可以到达数组的最后⼀个位置）。
 * 示例 1:
 * 输⼊：nums = [2,3,1,1,4]
 * 输出：2
 * 解释：跳到最后⼀个位置的最⼩跳跃数是 2。
 *  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后⼀个位置。
 * @version: 1.0
 */
public class LC_45跳跃游戏 {

	public static Boolean jump(int[] nums) {
		int n = nums.length;
		int end = 0, farthest = 0;
		int jumps = 0;

		for(int i = 1; i < n - 1; i++) {
			farthest = Math.max(farthest, i + nums[i]);
			if(farthest <= i) {// 到达当前最远距离，只能跳一次，更新最远距离
				return false;
			}
		}
		return farthest >= n - 1;// 返回最多活动数
	}

	public static void main(String[] args) {

//		int[] nums = {3,2,1,0,4};
		int[] nums = {2,3,1,1,4};
		System.out.println(jump(nums));
	}

}
